package algorithm.leetcode

object StepWays {
    /**
     * 3 => 4
     * 8 8 8
     */
    fun waysToStep(n: Int): Int {
        if(n == 1) return 1
        if(n == 2) return 2
        val ir = IntArray(n+1)
        ir[0] = 1
        ir[1] = 1
        ir[2] = 2
        var s = 3
        while (s <= n){
            val ct = (ir[s-1] + ir[s-2])%1000000007 + ir[s-3]
            ir[s] = ct % 1000000007
            s++
        }
        return ir[s-1]
    }
}

fun main() {
    println(StepWays.waysToStep(61))
}